#include<bits/stdc++.h>
using namespace std;
#define N 2005
#define int long long
int dp[N][N],a[N*105],dp2[N*105][15],n;
void solve1(){
    for(int i=1;i<n;i++)
        for(int j=0;j<i;j++){
            dp[i+1][j]=max(dp[i+1][j],dp[i][j]+(a[i]==a[i+1])*a[i]);
            dp[i+1][i]=max(dp[i+1][i],dp[i][j]+(a[j]==a[i+1])*a[j]);
        }
    int ans=0;
    for(int i=0;i<=n;i++)ans=max(ans,dp[n][i]);
    cout<<ans<<endl;
}
void solve2(){
    for(int i=1;i<n;i++)
        for(int j=0;j<11;j++){
            dp2[i+1][j]=max(dp2[i+1][j],dp2[i][j]+(a[i]==a[i+1])*a[i]);
            dp2[i+1][a[i]]=max(dp2[i+1][a[i]],dp2[i][j]+(j==a[i+1])*j);
        }
    int ans=0;
    for(int i=0;i<11;i++)ans=max(ans,dp2[n][i]);
    cout<<ans<<endl;
}
void solve(){
    cin>>n;
    int mf=0;
    for(int i=1;i<=n;i++)cin>>a[i],mf=max(mf,a[i]);
    memset(dp,0xc0,sizeof(dp)),memset(dp2,0xc0,sizeof(dp2)),dp[1][0]=dp2[1][0]=0;
    if(mf<=10)solve2();
    else if(n<=2000)solve1();
    else cout<<endl;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    freopen("color.in","r",stdin),freopen("color.out","w",stdout);
    int t;
    cin>>t;
    while(t--)solve();
}
